package kyssion.introductionToAlgorithms.chapter_04;

import kyssion.leetcode.util.ShowUtil;

/**
 * 算法导论分治策略这一章节的第一个例子
 * 描述给一个数组,让你求这个数组中连续的一段最大的和和其实位置
 */
public class Alorithms_4_001最大子数组 {

    public static void main(String[] args) {
        int[] ints =new Alorithms_4_001最大子数组().getMaxArr(
                new int[]{
                        13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7
                }
        );
        ShowUtil.showArr(ints);
    }

    /**
     * 本章的解法,使用分治方法实现对应的策略
     *
     * @param arr
     * @return
     */
    public int[] getMaxArr(int[] arr) {
        return ans(arr, 0, arr.length - 1);
    }

    public int[] ans(int[] arr, int start, int end) {
        if (start >= end) {
            return new int[]{
                    start, end, arr[start]
            };
        }
        int midle = (start + end) >> 1;
        // 0 1 0
        int[] left = ans(arr, start, midle);
        int[] right = ans(arr, midle + 1, end);
        int max = Integer.MIN_VALUE;
        int all = 0;
        int[] mil = new int[3];
        for (int a = midle; a >= midle; a--) {
            all = all + arr[a];
            if (all > max) {
                max = all;
                mil[0] = a;
                mil[2] = max;
            }
        }
        all = 0;
        max = Integer.MIN_VALUE;
        for (int a = midle + 1; a <= end; a++) {
            all = all + arr[a];
            if (all > max) {
                max = all;
                mil[1] = a;
            }
        }
        mil[2] = mil[2] + max;
        if (mil[2] > left[2]) {
            if (mil[2] > right[2]) {
                return mil;
            } else {
                return right;
            }
        } else {
            if (left[2] > right[2]) {
                return left;
            } else {
                return right;
            }
        }
    }

    /**
     * 动态规划解法
     *
     * @param arr
     * @return
     */
    public int[] ans(int[] arr) {
        int[][] dp = new int[arr.length][3];
        for (int a = 0; a < arr.length; a++) {
            if (a == 0 || arr[a] > dp[a - 1][2] + arr[a]) {
                dp[a][2] = arr[a];
                dp[a][0] = a;
                dp[a][1] = a;
            } else {
                dp[a][2] = dp[a - 1][2] + arr[a];
                dp[a][0] = dp[a - 1][0];
                dp[a][1] = a;
            }
        }
        int index = 0;
        for (int a = 1; a < arr.length; a++) {
            if (dp[a][2] > dp[index][2]) {
                index = a;
            }
        }
        return dp[index];
    }
}
